package 剑指Offer专项突破;

import java.util.*;

/**
 * @Author zhang lei
 * @Date 2022-05-06 20:29
 */
public class Algo060 {

    /**
     * 060 出现频率最高的k个数字
     * @param nums
     * @param k
     * @return
     */
    public static int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.merge(num, 1, Integer::sum);
        }

        PriorityQueue<Map.Entry<Integer, Integer>> pq = new PriorityQueue<>(Comparator.comparingInt(Map.Entry::getValue));

        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            //注意这里先添加，再移除
            pq.add(entry);
            if(pq.size()>k) {
                pq.poll();
            }
        }
        int[] result = new int[k];
        int i=0;
        while (pq.size()>0) {
            result[i++] = pq.poll().getKey();
        }
        return result;
    }


    /**
     * 061 和最小的k个数对
     * @param nums1
     * @param nums2
     * @param k
     * @return
     */
    public static List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        PriorityQueue<List<Integer>> pa = new PriorityQueue<>(
                ((o1, o2) -> o2.stream().mapToInt(Integer::intValue).sum() - o1.stream().mapToInt(Integer::intValue).sum()));
        for (int i = 0; i < Math.min(k, nums1.length); i++) {
            for (int j = 0; j < Math.min(k, nums2.length); j++) {
                pa.add(List.of(nums1[i],nums2[j]));
                if(pa.size()>k) {
                    pa.poll();
                }
            }
        }

        List<List<Integer>> result = new LinkedList<>();
        while (pa.size()>0) {
            result.add(pa.poll());
        }
        return result;
    }

    public static List<List<Integer>> kSmallestPairs2(int[] nums1, int[] nums2, int k) {
        return new ArrayList<>();
    }


    public static void main(String[] args) {
        System.out.println(kSmallestPairs2(new int[]{1,2}, new int[]{3}, 3).toString());
    }
}
